#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[2] = { -1, 0 };
    int dy[2] = { 0, -1 };
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid[0].size(), mod = 1e9 + 7;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(k)));
        dp[0][0][grid[0][0] % k] = 1;
        for (int i = 1; i < n; i++)
            for (int o = 0; o < k; o++) if (dp[i - 1][0][o]) dp[i][0][(o + grid[i][0]) % k] = dp[i - 1][0][o];
        for (int j = 1; j < m; j++)
            for (int o = 0; o < k; o++) if (dp[0][j - 1][o]) dp[0][j][(o + grid[0][j]) % k] = dp[0][j - 1][o];
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                for (int p = 0; p < 2; p++) {
                    int a = i + dx[p], b = j + dy[p];
                    for (int o = 0; o < k; o++) if (dp[a][b][o]) dp[i][j][(o + grid[i][j]) % k] = (dp[i][j][(o + grid[i][j]) % k] + dp[a][b][o]) % mod;
                }
            }
        // for(int i = 0; i < n; i++) {
        //     for(int j = 0; j < m; j++) {
        //         for(int o = 0; o < k; o++) cout << dp[i][j][o] << ' ';
        //         cout << endl;
        //     }
        //     cout << endl;
        // }
        return dp[n - 1][m - 1][0];
    }
};